.SS(Representation of LISP primitives,,P26:)
.SELECT 1;
Now that we have some of the representational problems for Symbolic expressions
reasonably well in-hand we will look after the implementation of the
of the LISP primitives. We will first examine %3car, cdr, eq%* and %3atom%*
leaving %3cons%* for last.
We will describe these first four primitives in an graphical notation based 
informally on a language called AMBIT/G.

AMBIT/G⊗↓An ambit is half aminal, half hobbit. AMBIT/G also is an acronym
for Algebraic Manipulation By Identity Transformation/Graphical.←
is a graphical language for the description of both
data and algorithms.  We will explore  a few aspects of AMBIT,
using it only to  describe  the basic operation of LISP. AMBIT
is a powerful graphical language suitable for describing complicated
data structures and their manipulation. A crucial problem of non-numerical  
applications is the structuring of the data;
once the 
proper representation has been established a very simple program to 
manipulate the complex representation will often suffice. Thus
what appears to be a complicated algorithm is, in reality, 
better represented as a simple algorithm operating on complex data. 
A poor representation will lead to an inefficient program. 
When we think about writing a complex non-numerical program like a compiler,
a proof-checker, or a piece of a large system, we frequently draw pictures to 
help crystalize our ideas and to structure the data efficiently.
When faced with explaining a complex structure-manipulating
program to someone  we draw a picture. Clearly then, a graphical notation
for programming is worth exploring.  AMBIT is such a language.

First, the data representation in AMBIT is a generalization of the
%2box notation%* of LISP.
Instead of requiring that we draw all
nodes in a tree as boxes, we might convey more of our intuition
by drawing nodes of different shapes to represent nodes which contain
different kinds of information.  We do this already to some extent, writing
elements of pointer space and full word space respectively as.
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
		⊂αααααπααααα⊃			⊂αααααααααα⊃
		~     ~     ~			~          ~
		%ααααα∀ααααα$			%αααααααααα$
.END
even though on most machines  
both kinds of nodes map into the same kind of memory cell.
AMBIT/G exploits this generalization of shapes.
 This is interesting and useful notation but in 
itself gives us no new power.  The innovation is that we can
also describe our algorithms as graphical transformations.

The basic statements of the language are %2pattern-match-and-replacement%* 
rules.  
Patterns are described  as combinations of shapes and solid arrows.
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
	    ⊂αααα⊃
	    ~    ~
	    ↑    ↓
	    ~	⊂αααπααα⊃		⊂αααααα⊃
	    %αααβα# ~ #αβαααααα→ααααααα→~      ~
		%ααα∀ααα$		%αααααα$
.END
is a pattern which will match any two cells such that the first one
is in pointer space and its left half points to itself and its right
half points to the second cell which is an element of FWS (full Word Space).


If an instance of a pattern can be
found in the current state of the computation, then we will replace 
that instance with a new pattern.  
The only kind of replacement we will allow is the %2swinging%*
of an arrow so that its head moves from one node to another.  
Thus the new pattern differs from the old only in the positioning
of some of the arrows.
Where the arrow head strikes a node is immaterial; the origin of the tail
%2is%* important.
Arrows which are to modified in the pattern matching are dashed.
Thus:
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
	    ⊂αααα⊃
	    ~    ~
	    ↑    ↓
	    ~	⊂αααπααα⊃		⊂ααααααα⊃
	    %αααβα# ~ #αβααααα→αααααααα→~       ~
		%α↓α∀ααα$		%ααααααα$
		   			    ↑
		  % - → - - - → - - - → - - - 
.END
is a statement telling us to replace the left-hand arrow
with an arrow to the cell in FWS if the pattern-match is successful.

Finally, the individual statements are combined into an
algorithm by success and failure conditions.

.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
	⊂ααααααααπαααααααααααααααααααααααααααααα⊃
	~  foo   ~				~
	εαααααααα$				~
	~   ⊂αααα⊃				~
	~   ~    ~				~
	~   ~    ↓				εαααα→ xy1
	~   ~	⊂αααπααα⊃	⊂ααααααα⊃	~ S
	~   %αααβα# ~ #αβαα→ααα→~       ~	~
	~	%α↓α∀ααα$	%ααααααα$	~
	~	   		  ↑		εαααα→ xy2
	~	  % - → - - → - - -		~ F
	%ααααααααααααααααααααααααααααααααααααααα$
.END
The name of this block is %bfoo%*. If the pattern-match  and construction are
successful then we will exit the block via the arrow labeled %BS%* and
continue execution with the block  named %bxy1%*. If the match is unsuccesful
then we exit through the failure exit, %BF%*, and continue with
block %bxy2%*.

The general execution of a block can be described as follows:

.BEGIN INDENT 10,10;
First the data is selected. A match of the nodes and solid links is attempted.
If this match cannot be made an error has occurred and the failure exit %bF%* is
taken.

If the match %2is%* successful then the
constructions, designated by the dotted links, are performed.
These dotted links then become solid, and the success exit, %bS%*, is taken.
.END

Now we wish to apply these techniques to describing LISP primitives.
We first need to supply some conventions for passing arguments to these
primitives and we need to describe how values computed by functions are
to be returned. Recall our introduction of the pointer registers, %bAC%41%1
through %bAC%4n%1 on {yon(P140)}. We will use these registers now.
To represent the passing of values %3v%41%*,#...#v%4n%1 to an n-ary  
function %3f%* we will set the registers %bAC%41%1,#...#%bAC%4n%1 to point
to the representations of the respective values. When the function %3f%*
has successfully completed its computation, it is expected to set %bAC%41%1
to point to the representation of the final value. Nothing is assumed
about the state of the other %bAC%4i%1 registers.

For example, here's %3car%*:

.GROUP;
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
		⊂αααααπααααααααααααααααααααα⊃
		~ car ~			    ~
		εααααα$ 		    ~
		~     AC∞41 ∞*		         ~
		~  ⊂ααααααα⊃		    ~
		~  ~ ⊂ #   ~		    εαα→
		~  %   βααα$		    ~ S
		~    ~ ~       ⊂αααπααα⊃    ~
		~      %αααααα→~ # ~ # ~    ~
		~    ~	       %αβα∀ααα$    εαα→ error
		~     		 ↓	    ~ F
		~    % - - → - -→∞3O∞*         ~
		%ααααααααααααααααααααααααααα$

.END
.BEGIN CENTER;SELECT 2;
Algorithm for %3car%*
.END
.APART

Thus for successful completion %b%3car%1 expects %bAC%41%1 to be pointing
to a node in pointer space; otherwise we get an error. If the match
is successful then %bAC%41%1 is changed to point to whatever was pointed to
by the left-hand side of the selected cell.
The description of %3cdr%* is sufficiently similar that we leave it to the
reader. 

On {yon(P139)} we described the internal structure of LISP atoms. Using that
representation we can give a simple implementation for the predicate %3atom%*:
.GROUP;
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
		⊂ααααααπαααααααααααααααααααα⊃
		~ atom ~		    ~
		εαααααα$		    ~
		~     AC∞41 ∞*		        ~
		~  ⊂ααααααα⊃		    ~
		~  ~   #   ~		    εαα→ true
		~  %αααβααα$		    ~ S
		~      ~       ⊂αααπααα⊃    ~
		~      %αααααα→~ ∃ ~ # ~    ~
		~	       %ααα∀ααα$    εαα→ false
		~     		  	    ~ F
		%ααααααααααααααααααααααααααα$

.END
.BEGIN CENTER;SELECT 2;
Algorithm for %3atom%*
.END
.APART
In this diagram only an appropriate match need be found; no construction is done. If
the match is successful, we exit to the block named %btrue%*. 
This will only happen if %bAC%41%1 is pointing to an atom header.
The effect of %btrue%* should  set %bAC%41%1 to point at the 
atom %3T%*. If the match is not successful
then we go to %bfalse%* which should set %bAC%41%1 to point at
the atom %3NIL%*.

We can also describe an implementation of %3eq%*.
The predicate, ⊗→%3eq%*↔←, 
needs to check that its arguments --#i.e., the pointers in %bAC%41%1 and 
%bAC%42%1#-- reference the same atom.
Since atoms are stored uniquely, this will condition will hold when 
%bAC%41%1 and %bAC%42%1  point 
to the same location in memory and that location is an atom header.

.GROUP;
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
		⊂ααααααπαααααααααααααααααααα⊃
		~  eq  ~		    ~
		εαααααα$		    ~
		~     AC∞41∞*		        ~
		~  ⊂ααααααα⊃		    ~
		~  ~   #   ~		    εαα→ true
		~  %αααβααα$		    ~ S
		~      ↓       ⊂αααπααα⊃    ~
		~      ε→ααααα→~ ∃ ~ # ~    ~
		~      ↑       %ααα∀ααα$    εαα→ false
		~  ⊂ααα∀ααα⊃	  	    ~ F
		~  ~   #   ~	  	    ~
		~  %ααααααα$	  	    ~
		~     AC∞42∞*	  	        ~
		%ααααααααααααααααααααααααααα$

.END
.BEGIN CENTER;SELECT 2;
Algorithm for %3eq%*
.END
.APART

In most implementations
the check for atom-ness is suppressed and a simple address comparison
is made. Non-atomic S-expressions are not usually stored uniquely; Thus
in most implementations

←%3eq[(A . B);(A . B)]%* is usually false, but

←%3eq[x;x] %*is usually true for any %3x%*.

Please note that we are %2not%* changing the definition of %3eq%*. 
%3eq%* is still undefined for non-atomic arguments.
The preceding remarks deal only with the usual implementation of 
%3eq%*⊗↓Remember that coding tricks should be used like garlic
in cooking.←.

%3cons%*, the remaining LISP  primitive, requires more care than the
previous four.